


<!doctype html>
<html lang="zh" class="no-js">
  <head>
    
      <meta charset="utf-8">
      <meta name="viewport" content="width=device-width,initial-scale=1">
      
      
      
      <link rel="shortcut icon" href="../../assets/images/favicon.png">
      <meta name="generator" content="mkdocs-1.1, mkdocs-material-5.1.4">
    
    
      
        <title>实验概述 - 操作系统（2020秋季） | 哈工大（深圳）</title>
      
    
    
      <link rel="stylesheet" href="../../assets/stylesheets/main.c4007cdc.min.css">
      
        <link rel="stylesheet" href="../../assets/stylesheets/palette.8435c73a.min.css">
      
      
        
        
        <meta name="theme-color" content="#2196f3">
      
    
    
    
      
        <link href="https://fonts.gstatic.com" rel="preconnect" crossorigin>
        <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto:300,400,400i,700%7CRoboto+Mono&display=fallback">
        <style>body,input{font-family:"Roboto",-apple-system,BlinkMacSystemFont,Helvetica,Arial,sans-serif}code,kbd,pre{font-family:"Roboto Mono",SFMono-Regular,Consolas,Menlo,monospace}</style>
      
    
    
    
    
      
    
    
  </head>
  
  
    
    
    <body dir="" data-md-color-primary="blue" data-md-color-accent="blue">
  
    <input class="md-toggle" data-md-toggle="drawer" type="checkbox" id="__drawer" autocomplete="off">
    <input class="md-toggle" data-md-toggle="search" type="checkbox" id="__search" autocomplete="off">
    <label class="md-overlay" for="__drawer"></label>
    <div data-md-component="skip">
      
        
        <a href="#_1" class="md-skip">
          跳转至
        </a>
      
    </div>
    <div data-md-component="announce">
      
    </div>
    
      <header class="md-header" data-md-component="header">
  <nav class="md-header-nav md-grid" aria-label="">
    <a href="../.." title="操作系统（2020秋季） | 哈工大（深圳）" class="md-header-nav__button md-logo" aria-label="操作系统（2020秋季） | 哈工大（深圳）">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path d="M416 48v416c0 26.51-21.49 48-48 48H144c-26.51 0-48-21.49-48-48V48c0-26.51 21.49-48 48-48h224c26.51 0 48 21.49 48 48zm96 58v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42V88h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zM30 376h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6z"/></svg>

    </a>
    <label class="md-header-nav__button md-icon" for="__drawer">
      <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M3 6h18v2H3V6m0 5h18v2H3v-2m0 5h18v2H3v-2z"/></svg>
    </label>
    <div class="md-header-nav__title" data-md-component="header-title">
      
        <div class="md-header-nav__ellipsis">
          <span class="md-header-nav__topic md-ellipsis">
            操作系统（2020秋季） | 哈工大（深圳）
          </span>
          <span class="md-header-nav__topic md-ellipsis">
            
              实验概述
            
          </span>
        </div>
      
    </div>
    
      <label class="md-header-nav__button md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
      </label>
      
<div class="md-search" data-md-component="search" role="dialog">
  <label class="md-search__overlay" for="__search"></label>
  <div class="md-search__inner" role="search">
    <form class="md-search__form" name="search">
      <input type="text" class="md-search__input" name="query" aria-label="搜索" placeholder="搜索" autocapitalize="off" autocorrect="off" autocomplete="off" spellcheck="false" data-md-component="search-query" data-md-state="active">
      <label class="md-search__icon md-icon" for="__search">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M9.5 3A6.5 6.5 0 0116 9.5c0 1.61-.59 3.09-1.56 4.23l.27.27h.79l5 5-1.5 1.5-5-5v-.79l-.27-.27A6.516 6.516 0 019.5 16 6.5 6.5 0 013 9.5 6.5 6.5 0 019.5 3m0 2C7 5 5 7 5 9.5S7 14 9.5 14 14 12 14 9.5 12 5 9.5 5z"/></svg>
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </label>
      <button type="reset" class="md-search__icon md-icon" aria-label="" data-md-component="search-reset" tabindex="-1">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M19 6.41L17.59 5 12 10.59 6.41 5 5 6.41 10.59 12 5 17.59 6.41 19 12 13.41 17.59 19 19 17.59 13.41 12 19 6.41z"/></svg>
      </button>
    </form>
    <div class="md-search__output">
      <div class="md-search__scrollwrap" data-md-scrollfix>
        <div class="md-search-result" data-md-component="search-result">
          <div class="md-search-result__meta">
            
          </div>
          <ol class="md-search-result__list"></ol>
        </div>
      </div>
    </div>
  </div>
</div>
    
    
      <div class="md-header-nav__source">
        
<a href="https://gitee.com/hitsz-lab/os_lab" title="前往 GitHub 仓库" class="md-source">
  <div class="md-source__icon md-icon">
    
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><path d="M439.55 236.05L244 40.45a28.87 28.87 0 00-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 01-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 000 40.81l195.61 195.6a28.86 28.86 0 0040.8 0l194.69-194.69a28.86 28.86 0 000-40.81z"/></svg>
  </div>
  <div class="md-source__repository">
    HITSZ-OS-Course
  </div>
</a>
      </div>
    
  </nav>
</header>
    
    <div class="md-container" data-md-component="container">
      
        
      
      
        
          

<nav class="md-tabs" aria-label="" data-md-component="tabs">
  <div class="md-tabs__inner md-grid">
    <ul class="md-tabs__list">
      
        
  <li class="md-tabs__item">
    
      <a href="../.." class="md-tabs__link md-tabs__link--active">
        实验须知
      </a>
    
  </li>

      
        
      
        
      
        
      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab1/part1/" class="md-tabs__link">
          Lab1：xv6与Unix实用程序
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab2/part1/" class="md-tabs__link">
          Lab2：实现一个简单的shell
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab3/part1/" class="md-tabs__link">
          Lab3：锁机制的应用
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../part1/" class="md-tabs__link">
          Lab4：内存管理之伙伴系统
        </a>
      
    </li>
  

      
        
  
  
    <li class="md-tabs__item">
      
        <a href="../../lab5/part1/" class="md-tabs__link">
          Lab5：简单文件系统的设计与实现
        </a>
      
    </li>
  

      
    </ul>
  </div>
</nav>
        
      
      <main class="md-main" data-md-component="main">
        <div class="md-main__inner md-grid">
          
            
              <div class="md-sidebar md-sidebar--primary" data-md-component="navigation">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    <nav class="md-nav md-nav--primary" aria-label="" data-md-level="0">
  <label class="md-nav__title" for="__drawer">
    <a href="../.." title="操作系统（2020秋季） | 哈工大（深圳）" class="md-nav__button md-logo" aria-label="操作系统（2020秋季） | 哈工大（深圳）">
      
  
  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path d="M416 48v416c0 26.51-21.49 48-48 48H144c-26.51 0-48-21.49-48-48V48c0-26.51 21.49-48 48-48h224c26.51 0 48 21.49 48 48zm96 58v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42V88h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zm0 96v12a6 6 0 01-6 6h-18v6a6 6 0 01-6 6h-42v-48h42a6 6 0 016 6v6h18a6 6 0 016 6zM30 376h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6zm0-96h42v48H30a6 6 0 01-6-6v-6H6a6 6 0 01-6-6v-12a6 6 0 016-6h18v-6a6 6 0 016-6z"/></svg>

    </a>
    操作系统（2020秋季） | 哈工大（深圳）
  </label>
  
    <div class="md-nav__source">
      
<a href="https://gitee.com/hitsz-lab/os_lab" title="前往 GitHub 仓库" class="md-source">
  <div class="md-source__icon md-icon">
    
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512"><path d="M439.55 236.05L244 40.45a28.87 28.87 0 00-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 01-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 000 40.81l195.61 195.6a28.86 28.86 0 0040.8 0l194.69-194.69a28.86 28.86 0 000-40.81z"/></svg>
  </div>
  <div class="md-source__repository">
    HITSZ-OS-Course
  </div>
</a>
    </div>
  
  <ul class="md-nav__list" data-md-scrollfix>
    
      
      
      


  <li class="md-nav__item">
    <a href="../.." title="实验须知" class="md-nav__link">
      实验须知
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../env/" title="实验平台以及环境配置" class="md-nav__link">
      实验平台以及环境配置
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../Linux/" title="Linux开发环境基础知识" class="md-nav__link">
      Linux开发环境基础知识
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item">
    <a href="../../remote_env/" title="远程实验环境使用指南" class="md-nav__link">
      远程实验环境使用指南
    </a>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-5" type="checkbox" id="nav-5">
    
    <label class="md-nav__link" for="nav-5">
      Lab1：xv6与Unix实用程序
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab1：xv6与Unix实用程序" data-md-level="1">
      <label class="md-nav__title" for="nav-5">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab1：xv6与Unix实用程序
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab1/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-6" type="checkbox" id="nav-6">
    
    <label class="md-nav__link" for="nav-6">
      Lab2：实现一个简单的shell
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab2：实现一个简单的shell" data-md-level="1">
      <label class="md-nav__title" for="nav-6">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab2：实现一个简单的shell
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part3/" title="实验提示" class="md-nav__link">
      实验提示
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab2/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-7" type="checkbox" id="nav-7">
    
    <label class="md-nav__link" for="nav-7">
      Lab3：锁机制的应用
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab3：锁机制的应用" data-md-level="1">
      <label class="md-nav__title" for="nav-7">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab3：锁机制的应用
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab3/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab3/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab3/part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab3/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-8" type="checkbox" id="nav-8">
    
    <label class="md-nav__link" for="nav-8">
      Lab4：内存管理之伙伴系统
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab4：内存管理之伙伴系统" data-md-level="1">
      <label class="md-nav__title" for="nav-8">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab4：内存管理之伙伴系统
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part3/" title="实验步骤" class="md-nav__link">
      实验步骤
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
      
      
      


  <li class="md-nav__item md-nav__item--nested">
    
      <input class="md-nav__toggle md-toggle" data-md-toggle="nav-9" type="checkbox" id="nav-9">
    
    <label class="md-nav__link" for="nav-9">
      Lab5：简单文件系统的设计与实现
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M8.59 16.58L13.17 12 8.59 7.41 10 6l6 6-6 6-1.41-1.42z"/></svg>
      </span>
    </label>
    <nav class="md-nav" aria-label="Lab5：简单文件系统的设计与实现" data-md-level="1">
      <label class="md-nav__title" for="nav-9">
        <span class="md-nav__icon md-icon">
          <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
        </span>
        Lab5：简单文件系统的设计与实现
      </label>
      <ul class="md-nav__list" data-md-scrollfix>
        
        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part1/" title="实验概述" class="md-nav__link">
      实验概述
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part2/" title="实验原理" class="md-nav__link">
      实验原理
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part3/" title="实验要求" class="md-nav__link">
      实验要求
    </a>
  </li>

        
          
          
          


  <li class="md-nav__item">
    <a href="../../lab5/part4/" title="提交文档" class="md-nav__link">
      提交文档
    </a>
  </li>

        
      </ul>
    </nav>
  </li>

    
  </ul>
</nav>
                  </div>
                </div>
              </div>
            
            
              <div class="md-sidebar md-sidebar--secondary" data-md-component="toc">
                <div class="md-sidebar__scrollwrap">
                  <div class="md-sidebar__inner">
                    
<nav class="md-nav md-nav--secondary" aria-label="目录">
  
  
    
  
  
    <label class="md-nav__title" for="__toc">
      <span class="md-nav__icon md-icon">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12z"/></svg>
      </span>
      目录
    </label>
    <ul class="md-nav__list" data-md-scrollfix>
      
        <li class="md-nav__item">
  <a href="#_2" class="md-nav__link">
    实验目的
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#_3" class="md-nav__link">
    实验学时
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#_4" class="md-nav__link">
    内容概述
  </a>
  
</li>
      
        <li class="md-nav__item">
  <a href="#_5" class="md-nav__link">
    评测程序
  </a>
  
</li>
      
    </ul>
  
</nav>
                  </div>
                </div>
              </div>
            
          
          <div class="md-content">
            <article class="md-content__inner md-typeset">
              
                
                
                  
                
                
                <h1 id="_1">实验概述</h1>
<h2 id="_2">实验目的</h2>
<p>熟悉buddy allocator的用法以及实现原理。</p>
<h2 id="_3">实验学时</h2>
<p>本实验为4学时。</p>
<h2 id="_4">内容概述</h2>
<ol>
<li>
<p>对当前的xv6，进程文件描述符以静态数组的形式声明，长度为NFILE，导致进程打开文件数受限于
数组大小而非剩余内存。你的任务是将其修改为使用buddy allocator*动态地分配/释放
文件描述符。</p>
</li>
<li>
<p>buddy allocator(kernel/buddy.c)有个可改进的地方。目前对于每个大小的每一个内存块都会使用1个bit
指示其被占用或是被释放。现在要求将其改为1个比特表示一对内存块B1，B2的分配情况:
B1被分配 XOR B2被分配。</p>
</li>
</ol>
<p>*: 参见实验原理buddy allocator </p>
<h2 id="_5">评测程序</h2>
<p>本次评测使用alloctest程序（xv6下运行）。alloctest包含以下两部分：
* filetest：该测试会通过创建多个进程，每个进程打开多个文件的方式来打开总数
  多于NFILE的文件。未改动的xv6无法通过此测试。
* memtest：该测试会尝试获取尽可能多的内存，获取内存空间未达到特定值则失败。
  未被优化的buddy allocator无法通过此测试。</p>
<h1 id="_6">实验原理</h1>
<h2 id="buddy-allocator">buddy allocator</h2>
<h3 id="_7">内存块概述</h3>
<p>buddy allocator使用不同大小的内存块来管理内存。
假设buddy allocator需要管理16* 2^n个字节，那么我们
将会需要n+1种大小的内存块，每种内存块的大小和数量分别为：</p>
<table>
<thead>
<tr>
<th align="left">size层号</th>
<th align="left">块大小（byte）</th>
<th align="left">块数量</th>
</tr>
</thead>
<tbody>
<tr>
<td align="left">n</td>
<td align="left">16 * 2^n</td>
<td align="left">1</td>
</tr>
<tr>
<td align="left">n-1</td>
<td align="left">16 * 2^(n-1)</td>
<td align="left">2</td>
</tr>
<tr>
<td align="left">...</td>
<td align="left">...</td>
<td align="left">...</td>
</tr>
<tr>
<td align="left">1</td>
<td align="left">16 * 2^1</td>
<td align="left">2^(n-1)</td>
</tr>
<tr>
<td align="left">0</td>
<td align="left">16 * 2^0</td>
<td align="left">2^n</td>
</tr>
</tbody>
</table>
<p>每一个size层的内存块都会完全覆盖要管理的空间，同时也说明了不同size层的内存块对应的内存区间是存在重叠的。</p>
<p><img alt="alt buddy allocator overview" src="buddy_overview.svg" /></p>
<p>图1 buddy allocator内存块示意图。</p>
<p>可以看到，对任意 0&lt; i &lt;= n中的一个块，对应于size i-1中的两个小块（或者叫一对小块）。
像这样对应上层一个大块的一对小块，则被称为一对buddy。</p>
<p>每一个内存块都有两个属性值：
* alloc：当前块是否已被分配 
* split：当前块是否已被分裂（分裂的具体含义将在下文中体现）</p>
<p>对size 0 中的块则是例外，因为size 0的块是最小的块，不能被分裂，所以不含split。</p>
<p>每一个size层都会维护一个空闲块链表，并且会保证所有层的空闲块列表中的内存块没有重叠部分。
图1并未画出空闲块链表，但以黄色标出了所有的在链表中的内存块。</p>
<h3 id="_8">内存块分配过程</h3>
<p>下面将以一个例子讲述buddy_allocator的内存分配过程。假设被管理的内存大小为16* 2^4，则一开始，没有内存被分配出去时，内存块和空闲块链表状态如下图：</p>
<p><img alt="alt buddy allocator ideal init" src="ideal_init.svg" /></p>
<p>图2 理想状态下的buddy alloctor的初始状态。</p>
<p>为方便讲解，将每一个内存块记为（Ml-n，l表示所在层，n为其在所在层的排序，如
M2-3表示size 2层的第3块）</p>
<p>现在我们请求一个20字节的内存，buddy allocator会进行以下操作。
1. 找到满足要求的最小size层
   * <script type="math/tex">16\times2^0 < 20 < 16\times2^1</script>，所以最小size取第1层.
2. 从满足要求的最小层（第1层）的空闲块链表开始寻找空闲块，若没有则继续向上查找
   * 查找size 1 的free链表，链表为空
   * 查找size 2 的free链表，链表为空
   * 查找size 3 的free链表，链表为空
   * 查找size 4 的free链表，得到一个内存块M4-1
3. 如果不是满足要求的最小层（第1层）获得的内存块，则对当前块做分裂操作（即将该块的alloc和split
   记为1，并将该块对应的两个小块中拿出一块放入下层size的空闲链表，取另一块作为要返回的块）。
   如果分裂出来的块仍不是最小层中的块，则重复上述过程，直到得到最小层的块：
   * 分裂M4，得到M3-1，M3-2，将M3-2放入size 3的空闲链表
   * 分裂M3-1，得到M2-1，M2-2，将M2-2放入size 2的空闲链表
   * 分裂M2-1，得到M1-1，M1-2，将M1-2放入size 1的空闲链表
   * 标记M1-1 alloc = 1，返回M1-1</p>
<p>完成上述分配后，得到内存块和空闲块链表状态如下：
<img alt="alt buddy allcator ideal alloc 20" src="alloc_1.svg" /></p>
<p>图3 请求了20B后</p>
<p>图中标为黄色的内存块从上到下依次为：M3-2，M2-2，M1-2
size 1中第1个内存块即为最后被分配出去的M1-1</p>
<p>现在我们再请求一个40字节的内存，分配器需要执行的操作：
1. 找到满足要求的最小size层
   * <script type="math/tex">16\times2^1 < 40 < 16\times2^2</script>，所以最小size取第2层。
2. 从最小层开始寻找空闲块
   * size 2的空闲链表中找到空闲块，即上面的M2-2
3. 将取到的块进行分裂，直到得到最小层的块，再返回
   * M2-2已是size 2层的块，将M2-2的alloc 标记为1，返回M2-2</p>
<p>完成上述分配后，内存块和空闲块链表状态如下：
<img alt="alt buddy allocator ideal alloc 40" src="alloc_2.svg" /></p>
<p>图4 请求了40B后</p>
<p>内存块的分配过程总结如下：从满足要求的最小size层的空闲链表开始寻找空闲块，如果没有则向上
层寻找，找到后将大块不断分裂直到分裂出满足要求的最小层的块。如果找不到满足要求的块，则
返回null。</p>
<h3 id="_9">内存块释放过程</h3>
<p>下面再讲解内存释放的过程。假设此时我们要释放一开始请求20B时分配的内存块，则过程如下：
1. 从第1层开始，根据释放的地址，找到当前层所对应的内存块，并查看split位是否为1，如果不为1
   则向上找一层，直到所找到的块为split为1：
   * 所给地址在size 1层对应的块为第1块（M1-1），该块split为0，查找上一层
   * 所给地址在size 2层对应的块为第1块（M2-1），该块split为1，为要找的块
2. 将上一步中找到的块的下一层中与该地址对应的块的alloc记为0：
   * 所给地址在size (2-1)层中对应块为第1块（M1-1），将M1-1的alloc记为0
3. 如果上一步中的块的buddy也是未分配状态，则需要对这对buddy进行合并（将这一对buddy对应的大块的alloc和split都记为0，将buddy从空闲块链表中拿出），如果合并出的大块其buddy的alloc也为0，则继续进行上述合并过
   程，否则将此大块放入对应的空闲链表。
   * 上一步的块为M1-1，其buddy为M1-2，M1-2 alloc 为0，需要进行合并。先将M1-2从size 1
     的空闲块链表中取出，将M1-1和M1-2对应的大块M2-1的alloc和split记为0.
   * M2-1的buddy为M2-2，M2-2 alloc 为1，无法继续合并，将M2-1放入空闲链表</p>
<p>完成上述释放过程后，内存块和空闲块链表如下：</p>
<p><img alt="alt buddy alloctor ideal free 20" src="free_1.svg" /></p>
<p>图5 释放20B后</p>
<p>此时再释放之前请求40B时分配的内存块，过程如下：
1. 从第1层向上找到释放地址对应的split为1的块：
   * 所给地址在size 1层对应块为第3块（M1-3），该块split为0，查找上一层
   * 所给地址在size 2层对应块为第2块（M2-2），该块split为0，查找上一层
   * 所给地址在size 3层对应块为第1块（M3-1），该块split为1，为要查找的块
2. 将上一步中找到的块的下一层中与该地址对应的块的alloc记为0：
   * 所给地址在size 2层对应块为第2块（M2-2），将M2-2的alloc记为0
3. 合并空闲块直到不可合并
   * 上一步的块为M2-2，其buddy为M2-1，M2-1 alloc为0，需要进行合并。将M2-1从size 2
     的空闲链表中取出，将M2-1，M2-2对应的大块M3-1的alloc和split标记为0
   * M3-1 buddy 为 M3-2，M3-2 alloc为0，需要进行合并。将M3-2从size 3的空闲链表中取出，
     将M3-1，M3-2对应的大块M4-1的alloc和split标记为0 
   * M4-1 没有buddy，合并停止，将M4-1加入size 4空闲链表。</p>
<p>完成上述释放过程后，内存块和空闲块链表状态回到图2的状态。</p>
<h3 id="_10">代码中的内存块和空闲链表</h3>
<p>在代码中每个size层的信息都被存储在struct sz_info中：
<div class="highlight"><pre><span></span><code><span class="mi">1</span> <span class="k">struct</span> <span class="n">sz_info</span> <span class="p">{</span>
<span class="mi">2</span>   <span class="n">Bd_list</span> <span class="n">free</span><span class="p">;</span>
<span class="mi">3</span>   <span class="kt">char</span> <span class="o">*</span><span class="n">alloc</span><span class="p">;</span>
<span class="mi">4</span>   <span class="kt">char</span> <span class="o">*</span><span class="n">split</span><span class="p">;</span>
<span class="mi">5</span> <span class="p">};</span>
</code></pre></div>
* free：空闲块链表的链表头
* alloc：当前层的所有内存块的alloc。每个块只用一个bit，所以alloc指向的数组的大小为（当前层块数/8）字节，不满1字节部分按1字节算。
* split：当前层的所有内存块的split。每个块只用一个bit，所以alloc指向的数组的大小为（当前层块数/8）字节，不满1字节部分按1字节算。注意，第0层没有split，所以第0层的split指向NULL。</p>
<p>因为内存块只是一个管理时的概念，实际代码中没有内存块结构体，内存块的alloc和split属性都存储在对应的
struct sz_info中。</p>
<h3 id="buddy-allocator_1">非理想 buddy allocator</h3>
<p>上文在描述buddy allocator分配和释放内存时，假设buddy allocator所管理的空间是理想的，即整个<script type="math/tex">16\times2^4</script>字节的空间都是可用的。但是实际运行时并非如此。下面将展示实际运行时buddy allocator所管理的空间的真实情况。</p>
<h4 id="_11">元数据记录区</h4>
<p>每个size层都需要一个struct sz_info来记录当前层的数据，struct sz_info 中的alloc和split也需要分别另外分配一个数组来存放每个块的alloc和split信息。这些struct sz_info以及alloc/split数组则被称为元数据。而这些元数据并不是另外找地方放的，而是放置在待管理的空间的头部的。为了防止分配空间时把放元数据的块给交出去，所以会在分配器初始化时将元数据占用的区域记为已被分配。</p>
<p>标记完元数据的内存块和空闲块链表状态如下（假设元数据占用3个内存块）：
<img alt="alt buddy allocator meta" src="allocator_meta.svg" />
图6 标记元数据</p>
<h4 id="_12">无效区</h4>
<p>这里，我们将要管理的区域的大小记为real_size。在大多数情况下可能找不到整数n使得16 * 2^n = real_size。这种情况下，分配器会寻找一个n使得16 * 2^(n-1) &lt; real_size &lt; 16 * 2^n，使用这个n作为最大size层数。那么被覆盖到的区域中，后面会有一部分是无效的，因为real_size并没有这么大。在初始化时会将相关块记为已分配。</p>
<p>标记完元数据和无效区后，内存块和空闲块链表状态如下（假设real_size为<script type="math/tex">16\times2^4-32</script>)：
<img alt="alt buddy allocator invalid" src="allocator_invalid.svg" />
图7 标记无效区</p>
<h4 id="_13">非对齐地址</h4>
<p>之前我们提到，buddy allocator的最小内存块是16字节，为了方便管理，内存块的起始地址也是按16字节对齐的。但如果交给我们的地址空间并不是按16字节对齐的该怎么办呢？这个时候分配器会简单地裁掉不对齐的部分。因为头尾最多各被裁掉15字节，所以最多只有30字节的空间被浪费，这也是可以接受的，下图为裁掉头部未对齐空间的示例：</p>
<p><img alt="alt buddy allocator invalid" src="buddy_overview.svg" />
图8 没错，其实就是图1</p>
<p>图中base和end是初始化是给分配器的内存的起始地址和末地址。其中base没有对齐16字节，ROUNDUP(base)是base向上对齐到16字节后的值。</p>
<p>以上则是buddy allocator的工作原理介绍。
代码中bd_malloc()对应于分配过程，bd_free()对应于释放过程，bd_init()则主要做了以下工作：</p>
<ol>
<li>起始地址/末地址16字节地址对齐</li>
<li>初始化元数据区</li>
<li>标记元数据区</li>
<li>标记无效区</li>
<li>初始化各层空闲链表</li>
</ol>
<h1 id="_14">实验内容</h1>
<h2 id="_15">实验步骤</h2>
<ol>
<li>切到alloc分支。</li>
<li>移除kernel/file.c第19行中file[NFILE]的声明。</li>
<li>在filealloc中使用bd_malloc动态申请文件描述符。（提示3）</li>
<li>在fileclose中释放文件描述符。（提示1、提示2）</li>
<li>在xv6中运行alloctest，第一部分如果正确完成，filetest应显示OK。</li>
<li>理解buddy allocator的工作方式。（实验原理-buddy allocator）</li>
<li>思考为什么可以仅用一个bit表示一对buddy的alloc。（实验概述-内容概述-2）（提示6）</li>
<li>修改kernel/buddy.c，使用一个bit表示一对buddy的alloc状态。（提示5、提示7）</li>
<li>在xv6中运行alloctest，此时两个test都应显示OK。</li>
<li>在Linux中运行make grade，确保测评结果为100分。</li>
</ol>
<h2 id="_16">提示</h2>
<ol>
<li>fileclose可以被化简，因为此时不再需要ff。但不要单纯地删除ff，弄清楚ff的作用再动手化简。</li>
<li>fileclose仍需要锁上ftable.lock，因为f-&gt;ref需要这个锁保护。</li>
<li>bd_malloc不会将分配给你的内存清0，调用bd_malloc时注意初始化得到的内存。</li>
<li>可以使用bd_print 打印当前分配器的状态。</li>
<li>不要忘了将bd_init()中分配给struct sz_info的alloc 空间大小除以2。</li>
<li>建议结合内存块分配和释放的过程思考,即按正常的分配/释放流程到哪一步时会出现不同，如何解决。
   单从"怎么知道一个块有没有被分配"的思路思考或许会进入死胡同。</li>
<li>bd_init()中初始化各层空闲链表一步将会是难点。</li>
</ol>
<h1 id="_17">实验提交</h1>
<p>参考之前实验的提交方式。</p>
                
              
              
                


              
            </article>
          </div>
        </div>
      </main>
      
        
<footer class="md-footer">
  
  <div class="md-footer-meta md-typeset">
    <div class="md-footer-meta__inner md-grid">
      <div class="md-footer-copyright">
        
          <div class="md-footer-copyright__highlight">
            Copyright &copy; 2020 - 2021 哈尔滨工业大学（深圳）
          </div>
        
        Made with
        <a href="https://squidfunk.github.io/mkdocs-material/" target="_blank" rel="noopener">
          Material for MkDocs
        </a>
      </div>
      
    </div>
  </div>
</footer>
      
    </div>
    
      <script src="../../assets/javascripts/vendor.83fe6e3c.min.js"></script>
      <script src="../../assets/javascripts/bundle.7e1cb91c.min.js"></script><script id="__lang" type="application/json">{"clipboard.copy": "\u590d\u5236", "clipboard.copied": "\u5df2\u590d\u5236", "search.config.lang": "ja", "search.config.pipeline": "", "search.config.separator": "[\\uff0c\\u3002]+", "search.result.placeholder": "\u952e\u5165\u4ee5\u5f00\u59cb\u641c\u7d22", "search.result.none": "\u6ca1\u6709\u627e\u5230\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.one": "\u627e\u5230 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.other": "# \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c"}</script>
      
      <script>
        app = initialize({
          base: "../..",
          features: ["tabs"],
          search: Object.assign({
            worker: "../../assets/javascripts/worker/search.37585f48.min.js"
          }, typeof search !== "undefined" && search)
        })
      </script>
      
        <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML"></script>
      
    
  </body>
</html>